/**
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 *
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 *
 * 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
 *
 * 链接：https://leetcode.cn/problems/kth-largest-element-in-an-array
 * 思路：基于快速排序
 * 我们刚说了，partition 函数会将 nums[p] 排到正确的位置，使得 nums[lo..p-1] < nums[p] < nums[p+1..hi]：
 *
 * 这时候，虽然还没有把整个数组排好序，但我们已经让 nums[p] 左边的元素都比 nums[p] 小了，也就知道 nums[p] 的排名了。
 *
 * 那么我们可以把 p 和 k' 进行比较，如果 p < k' 说明第 k' 大的元素在 nums[p+1..hi] 中，如果 p > k' 说明第 k' 大的元素在 nums[lo..p-1] 中。
 *
 * 进一步，去 nums[p+1..hi] 或者 nums[lo..p-1] 这两个子数组中执行 partition 函数，就可以进一步缩小排在第 k' 的元素的范围，最终找到目标元素。
 */
class FindKthLargest {
    public int findKthLargest(int[] nums, int k) {
        int len=nums.length;
         k=len-k;
        int lo=0;
        int hi=len-1;
        while(lo<=hi) {
            int p=pattion(nums,lo,hi);
            if(p<k) {
                lo=p+1;
            } else if(p>k) {
                hi=p-1;
            } else{
                return nums[p];
            }
        }
        return -1;
    }
    public int pattion(int[] nums,int left,int right) {
        int i=left;
        int j=right;
        int pivot=nums[left];
        while(i<j) {
            while(i<j&&nums[j]>=pivot) {
                j--;
            }
            while(i<j&&nums[i]<=pivot) {
                i++;
            }
            swap(nums,i,j);
        }
        swap(nums,i,left);
        return i;
    }
    public void swap(int[] nums,int i,int j) {
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    } 
    
}